package arrAndstr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T15 {

    public static void main(String[] args) {
        int[] nums = new int[]{2, -3, 0, -2, -5, -5, -4, 1, 2, -2, 2, 0, 2, -4, 5, 5, -10};
        System.out.println(threeSum(nums));
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int len = nums.length;

        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) { // 排序好，如果与前一个值相等，结束避免重复
                continue;
            }
            twoSum(result, nums, i + 1, len - 1, -nums[i], nums[i]);
        }

        return result;
    }

    public static void twoSum(List<List<Integer>> result, int[] nums, int left, int right, int targetValue, int value) {
        int leftLookedValue = 1;
        int rightLookedValue = -1;
        while (left < right) {   // 不能相等
            int tempValue = nums[left] + nums[right];
            if (tempValue == targetValue) {
                result.add(Arrays.asList(value, nums[left], nums[right]));
                if (left < right) { // 这里的while循环移动内部指针，如果是tempValue==targetValue才触发的，则一定在其内部进行移动，而不是外部！
                    while (left< nums.length-1 && nums[left]==nums[left+1]) {
                        left++;
                    }
                    while (right > 0 && nums[right]==nums[right-1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            } else if (tempValue < targetValue) {
                left++;
            } else {
                right--;
            }
        }
    }
}
